'''
https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/description/
'''

from typing import List


class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        sorted_nums = sorted(nums)
        n = len(nums)
        l = r = -1
        for i in range(n):
            if nums[i] != sorted_nums[i]:
                l = i
                break
        for i in range(n - 1, -1, -1):
            if nums[i] != sorted_nums[i]:
                r = i
                break
        return r - l + 1 if r != l else 0

    '''
        2, 6, 4, 8, 10, 9, 15
        ✅ ✅ ❌ ✅ ✅ ❌ ✅   左到右
                        r
        ✅ ❌ ✅ ✅ ❌ ✅ ✅   右到左
            l           
    '''
    def findUnsortedSubarray2(self, nums: List[int]) -> int:
        sorted_nums = sorted(nums)
        n = len(nums)
        l, r = n, -1  # l 左侧都是达标的，r右侧都是达标的
        max_num = -float('inf')
        for i in range(n):
            if nums[i] >= max_num:
                max_num = nums[i]
            else:
                r = i
        min_num = float('inf')
        for i in range(n-1, -1, -1):
            if nums[i] <= min_num:
                min_num = nums[i]
            else:
                l = i
        return r - l + 1 if r != l else 0
